/// https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
pub struct Solution;

impl Solution {
    pub fn simple_sort(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        // slower:
        // let mut nums = nums1.clone();
        // nums.extend_from_slice(&nums2);
        let mut nums = [nums1, nums2].concat();
        nums.sort();
        let mid = nums.len() / 2;
        if nums.len() % 2 == 1 {
            nums[mid] as f64
        } else {
            (nums[mid - 1] + nums[mid]) as f64 / 2.
        }
    }

    /// https://rustgym.com/leetcode/4
    pub fn dichotomy_faster(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let n1 = nums1.len();
        let n2 = nums2.len();
        if n1 < n2 {
            return Self::dichotomy_faster(nums2, nums1);
        }
        let mut lo = 0;
        let mut hi = n2 * 2;
        while lo <= hi {
            let mid2 = (lo + hi) / 2;
            let mid1 = n1 + n2 - mid2;
            let l1 = if mid1 == 0 { std::i32::MIN } else { nums1[(mid1 - 1) / 2] };
            let l2 = if mid2 == 0 { std::i32::MIN } else { nums2[(mid2 - 1) / 2] };
            let r1 = if mid1 == n1 * 2 { std::i32::MAX } else { nums1[mid1 / 2] };
            let r2 = if mid2 == n2 * 2 { std::i32::MAX } else { nums2[mid2 / 2] };

            if l1 > r2 {
                lo = mid2 + 1;
            } else if l2 > r1 {
                hi = mid2 - 1;
            } else {
                return (l1.max(l2) + r1.min(r2)) as f64 / 2.0;
            }
        }
        panic!()
    }

    /// https://github.com/SmiteWindows/leetcode/blob/mod/leetcode/src/array/leetcode4.rs
    pub fn dichotomy(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let m = nums1.len();
        let n = nums2.len();

        if m > n {
            return Self::dichotomy(nums2, nums1);
        }

        let mut i_min = 0;
        let mut i_max = m;
        let half_len = (m + n + 1) / 2;

        while i_min <= i_max {
            let i = (i_max + i_min) / 2;
            let j = half_len - i;

            if i < i_max && nums2[j - 1] > nums1[i] {
                i_min = i + 1;
            } else if i > i_min && nums1[i - 1] > nums2[j] {
                i_max = i - 1;
            } else {
                let max_left = if i == 0 {
                    nums2[j - 1]
                } else if j == 0 {
                    nums1[i - 1]
                } else {
                    nums1[i - 1].max(nums2[j - 1])
                };

                if (m + n) % 2 == 1 {
                    return max_left.into();
                }

                let min_right = if i == m {
                    nums2[j]
                } else if j == n {
                    nums1[i]
                } else {
                    nums2[j].min(nums1[i])
                };

                return (max_left + min_right) as f64 / 2.0;
            }
        }
        0.0
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>, Vec<i32>) -> f64 {
        assert_eq!(f(vec![1, 3], vec![2]), 2.);
        assert_eq!(f(vec![1, 2], vec![3, 4]), 2.5);
        assert_eq!(f(vec![0, 0], vec![0, 0]), 0.);
        assert_eq!(f(vec![], vec![1]), 1.);
        assert_eq!(f(vec![2], vec![]), 2.);
    }

    bench!(assert Solution::simple_sort);
    bench!(assert Solution::dichotomy);
    bench!(assert Solution::dichotomy_faster);
}
